#include <stdio.h>
#include "single_linked_list.cpp"

// 两个递增次序排列的单链表 合并为一个递减链表
LinkedList MergeList(LinkedList &L1, LinkedList &L2) {
    LinkedList res;
    InitList(res); // 合并后的头结点
    LNode *ptr1 = L1->next, *ptr2 = L2->next;
    while (ptr1 != NULL || ptr2 != NULL)
    {
        LNode *cur; // 当前遍历的最小结点
        // 一个链表遍历完成 将剩余按顺序插入
        if (ptr1 == NULL) {
            cur = ptr2;
            ptr2 = ptr2->next;
        } else if (ptr2 == NULL)
        {
            cur = ptr1;
            ptr1 = ptr1->next;
        } else {
            // 找出两链表中较小的一个
            if(ptr1->data < ptr2->data) {
                cur = ptr1;
                ptr1 = ptr1->next;
            } else {
                cur = ptr2;
                ptr2 = ptr2->next;
            }
        } 
        // 头插
        cur->next = res->next;
        res->next = cur;
    }
    return res;
}

int main() {
    LinkedList L1;
    InitList(L1);

    LinkedList L2;
    InitList(L2);

    // 插入
    ListAppend(L1, 2);
    ListAppend(L1, 3);
    ListAppend(L1, 8);
    ListAppend(L1, 17);
    ListAppend(L1, 23);
    ListAppend(L1, 36);
    PrintList(L1);

    ListAppend(L2, 1);
    ListAppend(L2, 2);
    ListAppend(L2, 5);
    ListAppend(L2, 10);
    PrintList(L2);

    LinkedList res = MergeList(L1,L2);
    PrintList(res);

    return 0;
}